package leetcode_day._2021._202110;

import java.util.HashSet;
import java.util.Set;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/10/28 9:00
 * 重新排序得到 2 的幂
 * 给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
 * 如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
 * 算法：深度优先搜索
 * 将重排后的所有情况都列出来 -- 相当于暴力老实解法，很慢，转化成了字符串
 * -----------------------------------------------------------
 * 数字的范围是 0 ~ 9，可以先把 n 拥有的数字都统计出来
 * 然后将这些数字重组，这两种方法最终的目的都是一样的
 */
public class _28_869 {
    static Set<Integer> set = new HashSet<>();
    static {
        for (int i = 1; i < (int) 1e9 + 10; i *= 2) set.add(i);
    }

    int[] cnt = new int[10];
    int m;
    public boolean reorderedPowerOf2_perfect(int n) {
        while (n != 0) {
            ++cnt[n % 10];
            n /= 10;
            ++m;
        }
        return dfs_perfect(0, 0);
    }
    boolean dfs_perfect(int cur, int u) {
        if (u == m) return set.contains(cur);
        for (int i = 0; i < 10; i++) {
            if (cnt[i] != 0) {
                cnt[i]--;
                if ((i != 0 || cur != 0) && dfs_perfect(cur * 10 + i, u + 1)) return true;
                cnt[i]++;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new _28_869().reorderedPowerOf2(526));
    }

    public boolean reorderedPowerOf2(int n) {
        String s = n + "";
        boolean[] used = new boolean[s.length()];
        return dfs("", s, 0, used);
    }
    boolean dfs(String cur, String n, int len, boolean[] used) {
        if (len == n.length()) return set.contains(Integer.parseInt(cur));
        for (int i = 0; i < n.length(); i++) {
            if (used[i]) continue;
            char c = n.charAt(i);
            if ("".equals(cur) && c == '0') continue;
            used[i] = true;
            if (dfs(cur + c, n, len + 1, used)) return true;
            used[i] = false;
        }
        return false;
    }

}
